package exams.dp;

public class FibonacciSolution {

    /**
     * 斐波那契数列
     *
     * 大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
     * */
    public int fibonacci (int n) {
        // write code here
        if(n < 3) {
            return 1;
        }
        int pre = 1;
        int res = 1;
        for(int i = 3; i <= n; i++) {
            int temp = res;
            res = res + pre;
            pre = temp;
        }

        return res;
    }

    /**
     * 跳台阶
     *
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     * */
    public int jumpFloor (int number) {
        // write code here
        int cur = 1;
        int pre = 1;

        for(int i =2; i<=number; i++) {
            int temp = cur;
            cur = cur + pre;
            pre = temp;
        }

        return cur;
    }

    /**
     * 最小花费爬楼梯
     *
     * 给定一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 请你计算并返回达到楼梯顶部的最低花费。
     * */
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        int res = 0;
        int pre = 0;

        for(int i = 2; i <= cost.length; i++) {
            int temp = res;
            res = Math.min(cost[i-1] + res, cost[i-2] +pre);
            pre = temp;
        }

        return res;
    }

    /**
     * 把数字翻译成字符串
     *
     * 有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
     * 现在给一串数字，返回有多少种可能的译码结果
     *
     * 数据范围：字符串长度满足0<n≤90
     * 进阶：空间复杂度O(n)，时间复杂度O(n)
     * */
    public int convertNumToStr (String nums) {
        // write code here
        if("0".equals(nums)) {
            return 0;
        }

        int preRes = 1;
        int res = 1;

        for(int i=1; i<nums.length();i++) {
            if(nums.charAt(i) == '0') {
                res = 0;
            }
            int cb = Integer.valueOf("" + nums.charAt(i-1)+nums.charAt(i));
            if(cb <= 26) {
                int temp = res;
                res = res + preRes;
                preRes = temp;
            } else {
                preRes = res;
            }
        }

        return res;
    }

    /**
     * 连续子数组的最大和
     *
     * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
     * 数据范围:
     * 1<=n<=2×105
     * −100<=a[i]<=100
     * 要求:时间复杂度为O(n)，空间复杂度为O(n)
     * 进阶:时间复杂度为O(n)，空间复杂度为O(1)
     *
     * 输入：
     * [1,-2,3,10,-4,7,2,-5]
     * 返回值：
     * 18
     * 说明：
     * 经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
     *
     * */
    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int res = 0;
        int max = Integer.MIN_VALUE;

        for(int i =0;i<array.length; i++) {
            res = Math.max(array[i], res + array[i]);
            if(res > max) {
                max = res;
            }
        }

        return max;
    }

}
